/************************************
 * Author：Zhaoqiang Shen
 * Date：2018.03.11
 *《算法导论》（中文第三版）排序相关的code
 ************************************/

#include <iostream>
#include <climits>
#include <vector>

using std::cout;
using std::vector;

// Insertion sort
void insertSort(vector<int> &A) {
    // standard insertion sort in p10
    int key, j;
    for (size_t i=1; i<A.size(); ++i) {
        key = A[i];
        j = i-1;
        while (j>=0 && A[j]>key) {
            A[j+1] = A[j];
            --j;
        }
        A[j+1] = key;
    }
}

// Merge sort
void merge(vector<int> &A, int p, int q, int r) {
    int n1=q-p+1, n2=r-q;
    vector<int> LL(n1+1, 0), RR(n2+1, 0);
    for (int i=0; i<n1; ++i)
        LL[i] = A[p+i];
    for (int i=0; i<n2; ++i)
        RR[i] = A[q+1+i];
    LL[n1] = INT_MAX;
    RR[n2] = INT_MAX;
    int j=0, k=0;
    for (int i=p; i<=r; ++i) {
        if (LL[j] <= RR[k]) {
            A[i] = LL[j];
            ++j;
        } else {
            A[i] = RR[k];
            ++k;
        }
    }
}

void merge2(vector<int> &A, int p, int q, int r) {
    int n1=q-p+1, n2=r-q;
    vector<int> LL(n1, 0), RR(n2, 0);
    for (int i=0; i<n1; ++i)
        LL[i] = A[p+i];
    for (int i=0; i<n2; ++i)
        RR[i] = A[q+1+i];
    int i=p, j=0, k=0;
    while (j<n1 && k<n2) {
        if (LL[j] <= RR[k]) {
            A[i] = LL[j];
            ++j;
        } else {
            A[i] = RR[k];
            ++k;
        }
        ++i;
    }
    for (; j<n1; ++i, ++j)
        A[i] = LL[j];
    for (; k<n2; ++i, ++k)
        A[i] = RR[k];
}

void mergeSort(vector<int> &A, int p, int q) {
    if (q<=p) return;
    int r=(p+q)/2;
    mergeSort(A, p, r);
    mergeSort(A, r+1, q);
    merge(A, p, r, q);
    //merge2(A, p, r, q);
}

int main() {
    int n;
    cout << "Array Size:> ";
    std::cin >> n;

    int v;
    vector<int> A;
    cout << "Input Array:> ";
    for (int i=0; i<n; ++i) {
        std::cin >> v;
        A.push_back(v);
    }
    vector<int> B(A);

    if (!A.empty()) {
        mergeSort(A, 0, A.size()-1);
        cout << "MergeSort: ";
        for (int vv: A)
            cout << vv << " ";
        cout << std::endl;

        insertSort(B);
        cout << "InsertionSort: ";
        for (int vv: B)
            cout << vv << " ";
        cout << std::endl;

        size_t i;
        for (i=0; i<A.size(); ++i) {
            if (A[i]!=B[i]) break;
        }
        if (i<A.size()) {
            cout << "FAIL at " << i << std::endl;
        } else {
            cout << "OK!" << std::endl;
        }

        return 0;
    } else
        return 1;
}